﻿using System;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.Numerics;
using System.Collections;

namespace ProjectEulerSolutions
{
    /**
     * 
     * Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can separated into piles in exactly seven different ways, so p(5)=7.
OOOOO
OOOO   O
OOO   OO
OOO   O   O
OO   OO   O
OO   O   O   O
O   O   O   O   O

Find the least value of n for which p(n) is divisible by one million.

     * */
    class Problem78 : IProblem
    {
        Dictionary<int, BigInteger> cache = new Dictionary<int, BigInteger>();

        public string Calculate()
        {
            cache.Add(0, 1);
            cache.Add(1, 1);

            int n = 1; //tek tako

            while (true)
            {
                n++;
                BigInteger pn = 0;
                int k = 0;
                int n1 = 0;
                int n2 = 0;
                do
                {
                    k++;
                    n1 = n - k * (3 * k - 1) / 2;
                    n2 = n - k * (3 * k + 1) / 2;

                    int s = 1;
                    if (k % 2 == 0)
                        s = -1;
                    if (n1 > 0)
                        pn += s * cache[n1];
                    if (n2 > 0)
                        pn += s * cache[n2];
                } while (n1 >= 0 || n2 >= 0);

                cache.Add(n, pn % 1000000);
                if (pn % 1000000 == 0)
                    break;
            }

            return n.ToString();
        }

        public BigInteger Generate(int n)
        {
            if (n < 0)
                return 0;

            if (cache.ContainsKey(n))
                return cache[n];

            BigInteger pn = 0;
            for (int k = 1; k <= n; k++)
            {
                int n1 = n - k * (3 * k - 1) / 2;
                int n2 = n - k * (3 * k + 1) / 2;

                BigInteger p1 = Generate(n1);
                BigInteger p2 = Generate(n2);

                if (k % 2 == 0)
                    pn = pn - p1 - p2;
                else
                    pn = pn + p1 + p2;
            }

            cache.Add(n, pn);
            return pn;
        }
    }
}
